Tag:隨意刷-[50-100] LeetCode Problem

Source:

88. Merge Sorted Array

1.題意:

• Merge(合併)兩個已排列(由小至大)陣列(nums1、nums2)
• 建議採用In place方式(見程式碼comment)將num2併入num1
• num1 長度為m，num2 長度為n，合併元素為num1的前m個與num2的前n個

Note:

• In-place algorithm

  In computer science, an in-place algorithm is an algorithm
  which transforms input using no auxiliary data structure.
  aka 對num1、num2直接操作，不使用額外變數(記憶體)來輔助來取得結果

2.思路:

1. 非in place版-直觀解
   使用額外變數tmpList
   放m個到tmpList
   再放n個到tmpList
   清空nums1 ➔ .clear()
   Copy tmpList to nums1
   進行sort ➔ .sort()

2. 非in place版-merge sort の merge
   兩個指針 i, j 初始分別指向num1與num2的第0個位置，比較值的大小(由小的開始放)，
   放入較小的元素進輔助變數(ans)，直到num1或num2的結尾，
   也就是 i或j已指到end of array
   aka i指到m-1或j指到n-1
   接著放另一個還未到結尾的array進ans。
   清空nums1 ➔ .clear()，
   迴圈法將ans中的每個元素加入nums1。

3. in place版-參考Discuss神人解
   兩陣列取大放(m+n-1)位置，被取的往前(往值小)移動，
   同一時間最終合併陣列-num1的(m+n-1)值會往前移，直到num2的元素用完(n為0)。

3.程式碼:

[非in place版-直觀解]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        tmpList = []
        for i in range(m):
            tmpList.append(nums1[i])
        for j in range(n):
            tmpList.append(nums2[j])
            
        nums1.clear()
        for k in range(m+n):
            nums1.append(tmpList[k])
        nums1.sort()    
        print(nums1)    

[非in place版-merge sort の merge]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = 0
        j = 0
        ans = []
        while i<m and j<n:
            if nums1[i]<nums2[j]:
                ans.append(nums1[i])
                i+=1
            else:
                ans.append(nums2[j])
                j+=1
        
        print("i-j",i,j)
        
        while i<=(m-1):
            ans.append(nums1[i])
            i+=1
        while j<=(n-1):
            ans.append(nums2[j])
            j+=1
        nums1.clear()
        for k in ans:
            nums1.append(k)    

More Info. Python Program for Iterative Merge Sort

[in place版-參考Discuss神人解]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        while n:
            if m and nums1[m-1]>nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m-=1
            else:
                nums1[m+n-1] = nums2[n-1]
                n-=1

More Info. Beautiful Python Solution/Comments/@clarencechee

Result:

• Modify nums1 in-place version:
  
• Submissions:
  

Level:Easy